package com.dsa.linear;

/**
 * empty: head == tail
 * full:  (tail + 1) % len == head
 * LoopQueue
 *
 * @param <E>
 */
public class LoopQueue<E> implements Queue<E> {

    private E[] data;
    private int head, tail;
    private int size;

    public LoopQueue() {
        this(10);
    }

    public LoopQueue(int capacity) {
        data = (E[]) new Object[capacity + 1];
        head = tail = 0;
        size = 0;
    }

    @Override
    public void enQueue(E element) {
        if (isFull())
            resize(capacity() * 2);

        data[tail] = element;
        tail = (tail + 1) % data.length;
        size++;
    }


    @Override
    public E deQueue() {
        if (isEmpty())
            throw new IllegalStateException("LoopQueue isEmpty, No such Element");

        E oldValue = data[head];
        data[head] = null;
        head = (head + 1) % data.length;
        size--;
        if (size == capacity() / 4 && capacity() / 2 != 0)
            resize(capacity() / 2);
        return oldValue;
    }

    @Override
    public E head() {
        if (isEmpty())
            throw new IllegalStateException("LoopQueue isEmpty, No such Element");
        return data[head];
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    public int capacity() {
        return data.length - 1;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append(String.format("LoopQueue(size = %d, capacity = %d)\n", size, capacity()));
        sb.append("  head [");
        for (int i = head; i != tail; i = (i + 1) % data.length) {
            sb.append(data[i]);
            if ((i + 1) % data.length != tail) {
                sb.append(", ");
            }
        }
        sb.append("] tail");
        return sb.toString();
    }

    private void resize(int newCapacity) {
        E[] newData = (E[]) new Object[newCapacity + 1];
        for (int i = 0; i < size; i++) {
            newData[i] = data[(head + i) % data.length];
        }
        data = newData;
        head = 0;
        tail = size;
    }


    private boolean isFull() {
        return (tail + 1) % data.length == head;
    }

    private int nextPos() {
        return (tail + 1) % data.length;
    }
}
